/**
 * Copyright 2011 Joe Choi, All rights reserved.
 */
package tao.data.structure.tree;

import tao.pattern.observer.Observable;
import tao.pattern.observer.Observer;

/**
 * The Traversal interface define the way to traverse a tree in specific order
 * <br><br>
 * 
 * <b>Pre-Order</b>
 * <br>
 * To traverse a tree in Pre-Order always visit the node before its subtrees
 * <br><br>
 * 
 * <b>Post-Order</b>
 * <br>
 * To traverse a tree in Post-Order always visit its subtrees before the node itself
 * <br><br>
 * 
 * <b>In-Order</b>
 * <br>
 * To traverse a tree in In-Order always visit the an number of subtrees before the node 
 * and then visit the remaining subtrees
 * <br>
 * 
 * <b> Factor of In-Order </b><br>
 * The factor of In-Order traversal is a parameter which control how many subtrees visited
 * before its parent and hence determined how many subtrees be visited after its parent be visited.
 * <br>
 * Note that if the factor greater or equal to the number of subtrees, the behavior of In-Order
 * traversal is same as Post-Order. In contrast, if the factor is less or equal to zero, the 
 * behavior of In-Order traversal is same as Pre-Order
 * 
 * @author Joe Choi
 * 
 */
public interface Traversal<V> extends Observable<Traversal.Event<V>> {
	public void start();
	public enum Order { Pre, In, Post }
	
	/**
	 * To create an new Traversal 
	 */
	public interface Factory<V> {
		public Traversal<V> create();
	}
	
	/**
	 * The listener for traversal
	 */
	public interface Listener<V> extends Observer<Event<V>> {
		public void beforeTraverseSubtree(Event<V> event);
		public void afterTraverseSubtree(Event<V> event);
		public void traversedTree(Event<V> event);
	}
	
	/**
	 * The Adaptor for traversal
	 */
	public class Adaptor<V> implements Listener<V> {
		@Override
		public final void notified(Event<V> event) {
			switch(event.getType()) {
				case BeforeTraverseSubtree : beforeTraverseSubtree(event); break;
				case AfterTraverseSubtree : afterTraverseSubtree(event); break;
				case TraversedTree : traversedTree(event); break;
			}
		}

		@Override
		public void traversedTree(Event<V> event) {}

		@Override
		public void afterTraverseSubtree(Event<V> event) {}

		@Override
		public void beforeTraverseSubtree(Event<V> event) {}
	}
	
	/**
	 * The event which occurs in traversal
	 */
	public static class Event<V> {
		public enum Type { TraversedTree, BeforeTraverseSubtree, AfterTraverseSubtree }
		
		public Event(Type type, Tree<V> tree) {
			this.type = type;
			this.tree = tree;
		}
		
		public Tree<V> getTree() {
			return(tree);
		}
		
		public Type getType() {
			return(type);
		}
		
		private Tree<V> tree;
		private Type type;
	}
}